# -*- coding: utf-8 -*-
# 实现 strStr() 函数
# 给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回 -1
# 示例 1:
# 输入: haystack = "hello", needle = "ll"
# 输出: 2

# 示例 2:
# 输入: haystack = "aaaaa", needle = "bba"
# 输出: -1

# 说明:
# 当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题
# 对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与C语言的 strstr() 以及 Java的 indexOf() 定义相符


# 模式匹配算法
class Solution(object):
    def strStr(self, haystack, needle):
        """
        :type haystack: str
        :type needle: str
        :rtype: int
        """
        # next[i]的含义除了下标i所在的字符外，最大的重复字符串长度(仅仅指和i紧连的)
        # eg: "abcdabcmnp"
        # 求 next[5]
        # needle[0:6] -> "abcdab"
        # 排除i所在的字符 -> "abcda"
        # "abcda"
        #     "abcda"
        # 因为如上所示则next[5] = 1
        # 
        # 求next[8]
        # needle[0:9] -> "abcdabcmn"
        # 排除i所在的字符 -> "abcdabcm"
        # "abcdabcm"
        #     "abcdabcm"
        # 如上虽有最大重复字符串"abc"，可是因为有"m"把"abc"和needle[8]="n"隔开，所以next[8] = 0
        #
        # 另外还需要排除本身
        # 求next[4]
        # needle[0:5] = "abcda"
        # "abcd"
        # "abcd"
        # 如上，我们不能让next[4] = 4，算法要求我们排除这种情况的匹配
        #
        #
        # 算法的思路：
        # 算法核心的思想是递推
        # 假设在n是我们已经求得 next[n] = m，以此为基础我们求得next[n + 1]
        # eg: "abcdabcmnp" 已知next[5] = 1 求next[6]
        # 由next[5] = 1可知
        # needle[0:6] -> "abcdab"
        # "abcda"
        #     "abcda"
        # 而next[6]，needle[0:7] -> "abcdabc"
        # 也即求"abcdab"的最大重复字符串
        # 因为我们已知"abcda"的最大重复字符串
        # "abcdab"
        #     "abcdab"
        # 
        #
        # 上面是next[6] = next[5] + 1时的情况，如果next[6] != next[5] + 1是什么情况？
        # "abcadabcabm"
        # 求next[10]
        # 已知：
        # "abcadabca"
        #      "abcadabca"
        # 当我们有next[9]递推next[10]时 
        # needle[9] = "b"
        # needle[ next[9] ] = needle[4] = "d"
        # "abcadabcab"
        #      "abcadabca"
        # "b" != "d" 所以不能递推 next[10] = next[9] + 1
        # 这时我们可以根据next[9] = 4，继续递推
        # 已知：
        # "abca"
        #    "abca"
        # needle[9] = "b"
        # needle[ next[4] ] = needle[1] = "b"
        # "abcab"
        #    "abcab"

        # 求"abcadabcab"的最大重复字符串
        # t:"abcadabcab"
        # p:"abcadabcab"
        # p一直向右移动，第一个对应为全匹配的字符串即为最大重复字符串
        # t:"abcadabcab"
        #  p:"abcadabcab"
        # t:"abcadabcab"
        #   p:"abcadabcab"
        # t:"abcadabcab"
        #    p:"abcadabcab"
        # t:"abcadabcab"
        #     p:"abcadabcab"
        # t:"abcadabcab"
        #      p:"abcadabcab"
        # 以上的移动步骤被我们使用一直next[9]递推next[10]时直接跳过
        # 而这一步的含义也可以转变为
        # 求"abcab"的最大重复字符串
        # t:"abcab"
        # p:"abcab"
        # p一直向右移动，第一个对应为全匹配的字符串即为最大重复字符串
        # 又可以再次进行简化
        # ......

        # 算法中使用了一个小技巧 即next[0] = -1
        # 1、避免了上面所说的和本身匹配的问题next[0] = -1则next[1] = 0，因为是递推关系所以当next[1] = 0没有和自身匹配，之后再也不会和自身匹配了
        # 2、方便next[i] = next[index] + 1对于next[i] = 0这个边界的实现
        if len(needle) == 0:
            return 0;
            
        next = [-1] * len(needle);
        for i in xrange(1, len(needle)):
            index = i - 1;
            while next[index] != -1 and needle[ next[index] ] != needle[i - 1]:
                index = next[index];
            next[i] = next[index] + 1;
        j = 0;
        for i in xrange(0, len(haystack)):
            while j != -1:
                if haystack[i] == needle[j]:
                    break;
                j = next[j];
            j += 1;
            if j == len(needle):
                return i - j + 1;
        return - 1;


t = Solution();
print t.strStr("hello", "ll");